#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 素数线性筛

// 是否不是素数
bool isNPrime[5000];

// 素数列表
int primes[5000];
int tot;

// 后缀添加
int slis[5000];
// 约数个数函数
int tao[5000];

int v[5000];

// 计算约数个数函数
void sieve_tao(int n)
{
    tao[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!isNPrime[i])
        {
            primes[tot++] = i;
            slis[i] = 1;
            tao[i] = 2;
        }
        for (int j = 0, val; j < tot && (val = i * primes[j]) <= n; j++)
        {
            isNPrime[val] = true;
            if (i % primes[j])
            {
                slis[val] = i;
                tao[val] = tao[i] * 2;
            }
            else
            {
                slis[val] = slis[i];
                tao[val] = tao[i] + tao[slis[i]];
                break;
            }
        }
    }
}

// 计算最小质因子，以便于 O(logn) 分解质因数

void sieve_v(int n)
{
    v[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!isNPrime[i])
        {
            primes[tot++] = i;
            v[i] = i;
        }
        for (int j = 0, val; j < tot && (val = i * primes[j]) <= n; j++)
        {
            isNPrime[val] = true;
            v[val] = primes[j];
            if (!(i % primes[j]))
                break;
        }
    }
}
